package ru.eas.fibonachi;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * @author aesipov
 */
public class Fibonachi2Devide {
    public static void main(String[] args)
    {
//        Scanner scanner = new Scanner(System.in);
//        long n = scanner.nextInt();
//        int m = scanner.nextInt();

        long n = 18825555099925889L;
        int m = 60414;
        System.out.println(fib2LastDigit(n, m));
    }

    private static long fib2LastDigit(long n, int m) {
        if (n <= Integer.MAX_VALUE) {
            long[] array = new long[(int) n + 1];
            array[0] = 0;
            array[1] = 1;
            for (int i = 2; i < array.length; i++) {
                array[i] = (array[i - 1] + array[i - 2]) % 10;
            }
            return array[(int) n ];
        } else {

            long[] array1 = new long[Integer.MAX_VALUE];
            array1[0] = 0;
            array1[1] = 1;
            for (int i = 2; i < array1.length; i++) {
                array1[i] = (array1[i - 1] + array1[i - 2]) % m;
            }
            long[] array2 = new long[(int)(n - Integer.MAX_VALUE)];
            array2[0] = array1[Integer.MAX_VALUE - 1] + array1[Integer.MAX_VALUE];
            array2[1] = array2[0] + array1[Integer.MAX_VALUE];
            for (int i = 2; i < array2.length; i++) {
                array2[i] = (array2[i - 1] + array2[i - 2]) % m;
            }
            return array2[array2.length - 1];
        }


    }
}
